package com.cqs.leetcode.recursion;

import java.util.HashSet;
import java.util.Set;

public class NQueensII52 {

    static class Solution {
        private int[] col;
        private int[] cross;
        // "\"方向对角线的会出现负数，为了方便处理，使用set存储
        private Set<Integer> cross2 = new HashSet<>();
        //案数量
        private int result = 0;

        public int totalNQueens(int n) {
            if (n <= 1) return n;
            col = new int[n];
            cross = new int[2 * n - 1];
            totalNQueens(n, 0);
            return result;
        }


        public void totalNQueens(final int n, int level) {
            if (level == n) {
                ++result;
                return;
            }
            for (int i = 0; i < n; i++) {
                //处理列
                if (col[i] == 1) continue;
                // "/"对角线
                if (cross[level + i] == 1) continue;
                // "\"对角线
                if (cross2.contains(level - i)) continue;
                col[i] = 1;
                cross[level + i] = 1;
                cross2.add(level - i);
                totalNQueens(n, level + 1);
                col[i] = 0;
                cross[level + i] = 0;
                cross2.remove(level - i);
            }
        }
    }


   private boolean[] cell, pie, na;

    int sum = 0;

    public int totalNQueens(int n) {
        if (n <= 1) return n;
        //N 列
        cell = new boolean[n];
        // x条 撇条对角线
        pie = new boolean[2 * n - 1];
        //X条 捺对角线
        na = new boolean[2 * n - 1];
        queens(n, 0);
        return sum;
    }

    private void queens(int n, int row) {
        if (n == row) {
            ++sum;
            return;
        }
        //没列逐渐放位置
        for (int i = 0; i < n; ++i) {
            if (cell[i] || na[row + i] || pie[row - i + n - 1]) continue;
            cell[i] = na[row + i] = pie[row - i + n - 1] = true;
            queens(n, row + 1);
            //回溯
            cell[i] = na[row + i] = pie[row - i + n - 1] = false;
        }
    }

    public static void main(String[] args) {
        NQueensII52 queensII52 = new NQueensII52();
        Solution solution = new Solution();
        for (int i = 0; i < 20; i++) {
            int qr = queensII52.totalNQueens(i);
            int sr = solution.totalNQueens(i);
            System.out.println(i + "\t" + qr + "\t" + sr);
        }
    }
}
